package gold.digger;

import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC99 {

    public TreeNode first = null;
    public TreeNode second = null;
    public TreeNode prev = null;

    public void recoverTree(TreeNode root) {
        inOrderTraverse(root);
        swap(first, second);
    }

    public void inOrderTraverse(TreeNode cur) {
        if (cur == null) {
            return;
        }

        inOrderTraverse(cur.left);
        if (null != prev && cur.val < prev.val) {
            if (null == first) first = prev;
            second = cur;
        }

        prev = cur;
        inOrderTraverse(cur.right);
    }


    public void swap(TreeNode first, TreeNode second) {
        int temp = second.val;
        second.val = first.val;
        first.val = temp;
    }

    public void run() {
        TreeNode a = new TreeNode(5);
        TreeNode b = new TreeNode(3);
        TreeNode c = new TreeNode(9);
        TreeNode d = new TreeNode(-2147483648);
        TreeNode e = new TreeNode(2);

        a.left = b;
        a.right=c;

        b.left = d;
        b.right=e;
        recoverTree(a);
    }


    public static void main(String[] args) {
        LC99 an = new LC99();
        an.run();
    }
}
